def pre_sum(a):
    n=len(a)
    sum=[0]*n
    sum[0]=a[0]%mod
    for i in range(1,n):
        sum[i]=(sum[i-1]+a[i])%mod
    return sum

# 求区间的前缀和
def get_sum(sum,l,r):
    if l==0:
        return sum[r]
    else:
        return (sum[r]-sum[l-1]+mod)%mod

n,m=map(int,input().split())
a=list(map(int,input().split()))
mod=1000000007
# 存储a数据的前缀和，a数组平方的前缀和
sum_a=[]
for i in range(1,6):
    tem_a=[x**i for x in a]
    sum_a.append(pre_sum(tem_a))

for _ in range(m):
    l,r,k=map(int,input().split())
    print(get_sum(sum_a[k-1],l-1,r-1))
